package problem300;

import java.util.ArrayList;
import java.util.List;

//300. 最长递增子序列
//https://leetcode.cn/problems/longest-increasing-subsequence/description/
//贪心解法

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        for(int i = 1; i<n; i++) {
            if(nums[i] > list.get(list.size()-1)) {
                list.add(nums[i]);
            }else {
                int index = search(list, nums[i]);
                list.set(index, nums[i]);
            }
        }
        return list.size();
    }
    private int search(List<Integer> list, int tar) {
        int l = 0, r = list.size()-1;
        while(l < r) {
            int m = l + (r-l)/2;
            if(list.get(m) < tar) {
                l = m + 1;
            }else {
                r = m;
            }
        }
        return l;
    }
}